package 力扣算法练习.main1.part1;

import java.util.HashMap;
import java.util.Map;

public class day5 {
    /*
    例如， 罗马数字 2 写做II，即为两个并列的 1。12 写做XII，即为X+II。 27 写做XXVII, 即为XX+V+II
    4 不写做IIII，而是IV。数字 1 在数字 5 的左边，所表示的数等于大数
     5 减小数 1 得到的数值 4 。同样地，数字 9 表示为IX。这个特殊的规
     则只适用于以下六种情况：
    I可以放在V(5) 和X(10) 的左边，来表示 4 和 9。
    X可以放在L(50) 和C(100) 的左边，来表示 40 和90。
    C可以放在D(500) 和M(1000) 的左边，来表示400 和900。
    给你一个整数，将其转为罗马数字。
    https://leetcode.cn/problems/integer-to-roman
     */
    int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

    public String intToRoman(int num) {
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < values.length; i++) {
            while (num >= values[i]) {
                result.append(symbols[i]);
                num -= values[i];
            }
        }
        return result.toString();
    }



    /*
    编写一个函数来查找字符串数组中的最长公共前缀。
    如果不存在公共前缀，返回空字符串 ""。
    https://leetcode.cn/problems/longest-common-prefix/
     */
    //时间复杂度 o(m*n)
    public String longestCommonPrefix(String[] strs) {
        //首先将第一个字符串的所有元素存入字符数组当中然后遍历其他字符串如果不相同就"删除"
        //拿公共的和每一个作比较
        int length=strs[0].length();
        char[] compare=new char[length];
        String temp=strs[0];
        int l1,index1=0,index2=0;
        for (int i=0;i<length;i++)compare[i]=temp.charAt(i);
        for (int i = 1; i < strs.length; i++) {
            temp=strs[i];
            l1=temp.length();
            if(length<=0||l1==0)return "";//可能存在空字符串
            while(index1<length&&index2<l1){
                if (compare[index1++]!=temp.charAt(index2++)){
                    length=index1-1;//因为上面的if比较以后index1有自增了一次就指向下一个位置了所以要减1
                }
                if (index2==l1&&length>l1)length=index2;
            }
            index1=0;
            index2=0;
        }
        StringBuilder result=new StringBuilder();
        for (int i = 0; i < length; i++) {
            result.append(compare[i]);
        }
        return result.toString();
    }

    //官方解 时间复杂度o(n*m)
    public String longestCommonPrefix1(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        int count = strs.length;
        for (int i = 1; i < count; i++) {
            prefix = longestCommonPrefix1(prefix, strs[i]);
            if (prefix.length() == 0) {
                break;
            }
        }
        return prefix;
    }

    public String longestCommonPrefix1(String str1, String str2) {
        int length = Math.min(str1.length(), str2.length());
        int index = 0;
        while (index < length && str1.charAt(index) == str2.charAt(index)) {
            index++;
        }
        return str1.substring(0, index);
    }


}
